Bối cảnh game dựa trên thời kỳ Edo ở Nhật Bản. Một vị tướng quân đã thống nhất Nhật Bản sau nhiều năm chiến tranh. Tuy nhiên, một lãnh chúa bí ẩn được gọi là Kage-sama đã xuất hiện, gây nguy hiểm cho sự ổn định của đất nước. Tướng quân bèn giao cho Oshiro Mugen, một samurai dưới trướng, tiêu diệt Kage-sama và các đồng minh của hắn. Xuyên suốt hành trình của mình, Mugen gặp gỡ và chiêu mộ 4 nguòi đồng hành chuyên thâm nhập và ám sát: Hayato, một ninja dữ tợn đến từ tỉnh Iga cũ; Yuki, một thanh niên thông minh, ham học hỏi bị ruồng bỏ; Aiko, một nữ ninja đến từ tỉnh Shinano và là tình nhân của Mugen; và Takuma, tay súng cừ khôi và nhà giả kim tài năng.

Cùng nhau, họ xác định danh tính và ra tay giết hai đồng minh của Kage-sama: Lãnh chúa Yabu và Tướng Okkoto. Tuy nhiên, khi họ cố gắng tóm Kage-sama thì chính họ lại bị bắt. Kage-sama không ai khác chính là Lãnh chúa Noboru, em trai của Tướng quân và là vị tướng cấp cao. Noboru không muốn hòa bình mà cứ để chiến tranh vĩnh viễn, nơi những chiến binh như hắn ta mới có đất dụng võ. Bắt giam những người bạn đồng hành của Mugen làm con tin, Noboru buộc Mugen dẫn hắn đến nơi ẩn náu bí mật của Ryunosuke, con trai của Tướng quân, người đã giết con trai của Noboru là Masaru. Những người bạn đồng hành của Mugen thoát khỏi nơi bị giam cầm, nhưng Mugen mang mặc cảm tội lỗi và bị sỉ nhục đã thực hiện nghi thức seppuku.

Sau khi biết rằng cả nhóm vẫn sống sót, Noboru đổ lỗi cho họ vì đã giết Ryunosuke và nảy ra kế hoạch ám sát Tướng quân. Cả nhóm bắt cóc Masaru và giao lại cho Tướng quân, để rồi hắn đành thú nhận tất cả mọi thứ về sự dính líu của mình trong âm mưu của cha hắn. Tướng quân xử tử Masaru và cử cả nhóm thực hiện nhiệm vụ cuối cùng là giết Noboru trong lâu đài của hắn. Sau khi trả thù cho Mugen, bốn người đồng đội chia tay nhau và biến mất khỏi con mắt của lịch sử. Aiko sau đó sinh con trai của Mugen, sau được Tướng quân nhận nuôi, cho phép con cháu Mugen kế tục anh ta tồn tại lâu dài.